package com.leetcode.algorithm.y18.m05;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * leetcode-cn.com
 * 326. 3的幂
 * 342. 4的幂
 * 344. 反转字符串
 * 345. 反转字符串中的元音字母
 * 349. 两个数组的交集 
 * 350. 两个数组的交集 II
 * 367. 有效的完全平方数
 * 242. 有效的字母异位词 
 * 258. 各位相加
 * 263. 丑数
 * 268. 缺失数字
 * 283. 移动零
 * 290. 单词模式
 * 389. 找不同
 * @author: jie.deng
 * @time: 2018年5月12日 上午11:40:30
 */
public class MySolution0512 {

	/**
	 * 326. 3的幂 
	 * 给出一个整数，写一个函数来确定这个数是不是3的一个幂。
	 * 
	 * 后续挑战： 
	 * 你能不使用循环或者递归完成本题吗？
	 * 
	 * @param n
	 * @return
	 */
	public boolean isPowerOfThree(int n) {
		if (n < 1) {
			return false;
		}
		while (n > 0) {
			if (n == 1) {
				return true;
			}
			int sum = n % 10; // 各位之和
			int i = n / 10;
			while (i > 0) {
				sum += i % 10;
				i /= 10;
			}
			if (sum % 9 == 0) {
				n /= 9;
			} else if (sum % 3 == 0) {
				n /= 3;
			} else {
				return false;
			}
		}
		return false;
//		return n > 0 && 1162261467 % n == 0;
	}
	
	public static void main(String[] args) {
		long num = 3;
		while (num * 3 < Integer.MAX_VALUE) {
			num *= 3;
		}
		System.out.println(num);
	}

	/**
	 * 342. 4的幂 
	 * 
	 * 给定一个整数 (32位有符整数型)，请写出一个函数来检验它是否是4的幂。
	 * 
	 * 示例: 
	 * 当 num = 16 时 ，返回 true 。 
	 * 当 num = 5时，返回 false。
	 * 
	 * 问题进阶：
	 * 你能不使用循环/递归来解决这个问题吗？
	 * 
	 * @param num
	 * @return
	 */
	public boolean isPowerOfFour(int num) {
		if (num < 1) {
			return false;
		}
		while (num > 0) {
			if (num == 1) {
				return true;
			}
			if ((num & 0x3) == 0) {
				num >>= 2;
			} else {
				return false;
			}
		}
		return false;
	}
	public boolean isPowerOfFourSolution(int num) {
		if (num < 1) {
			return false;
		}
		// 0b1、0b100、0b10000、...
		int len = Integer.toBinaryString(num).length();
		return len % 2 == 1 && (num & (num - 1)) == 0;
	}

	/**
	 * 344. 反转字符串
	 * 请编写一个函数，其功能是将输入的字符串反转过来。
	 * @param s
	 * @return
	 */
	public String reverseString(String s) {
//		return new StringBuffer(s).reverse().toString();
		if (null == s) {
			return s;
		}
		char[] chars = s.toCharArray();
		int len = chars.length;
		for (int i = 0; i < len - 1 - i; i++) {
			char tmp = chars[i];
			chars[i] = chars[len - 1 - i];
			chars[len - 1 - i] = tmp;
		}
		return new String(chars);
	}

	/**
	 * 345. 反转字符串中的元音字母 
	 * 编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
	 * 
	 * 示例 1： 给定 s = "hello", 返回 "holle".
	 * 
	 * 示例 2： 给定 s = "leetcode", 返回 "leotcede".
	 * 
	 * 注意: 元音字母不包括 "y".
	 * 
	 * @param s
	 * @return
	 */
	public String reverseVowels(String s) {
		if (null == s) {
			return s;
		}
		char[] chars = s.toCharArray();
		int len = chars.length;
		int i = 0;
		int j = len - 1;
		while (i < j) {
			while (i < j && !isVowels(chars[i])) {
				i++;
			}
			while (i < j && !isVowels(chars[j])) {
				j--;
			}
			if (i < j) {
				char tmp = chars[i];
				chars[i] = chars[j];
				chars[j] = tmp;
				i++;
				j--;
			}
		}
		return new String(chars);
	}

	private boolean isVowels(char c) {
		return c == 'a' || c == 'o' || c == 'e' || c == 'i' || c == 'u'
				|| c == 'A' || c == 'O' || c == 'E' || c == 'I' || c == 'U';
	}

	/**
	 * 349. 两个数组的交集 
	 * 给定两个数组，写一个函数来计算它们的交集。
	 * 
	 * 例子:
	 * 给定 num1= [1, 2, 2, 1], nums2 = [2, 2], 
	 * 返回 [2].
	 * 
	 * 提示:
	 * 每个在结果中的元素必定是唯一的。 
	 * 我们可以不考虑输出结果的顺序。
	 * @param nums1
	 * @param nums2
	 * @return
	 */
	public int[] intersection(int[] nums1, int[] nums2) {
		if (nums1.length == 0 || nums2.length == 0) {
			return new int[]{};
		}
		HashSet<Integer> set = new HashSet<Integer>();
		int[] numA;	//nums1和nums2中的短数组
		int[] numB; //nums1和nums2中的长数组
		if (nums1.length < nums2.length) {
			numA = nums1;
			numB = nums2;
		} else {
			numA = nums2;
			numB = nums1;
		}
		int[] nums = new int[numA.length];
		int idx = 0;

		for (int i = 0; i < numA.length; i++) {
			set.add(numA[i]);
		}
		for (int i = 0; i < numB.length; i++) {
			if (set.contains(numB[i])) {
				nums[idx++] = numB[i];
				set.remove(numB[i]);
				if (set.isEmpty()) {
					break;
				}
			}
		}
		return Arrays.copyOfRange(nums, 0, idx);
	}

	/**
	 * 350. 两个数组的交集 II 
	 * 给定两个数组，写一个方法来计算它们的交集。
	 * 
	 * 例如: 给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 
	 * 返回 [2, 2].
	 * 
	 * 注意：
	 * 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。 
	 * 我们可以不考虑输出结果的顺序。 
	 * 
	 * 跟进:
	 * 如果给定的数组已经排好序呢？你将如何优化你的算法？ 
	 * 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
	 * 如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？
	 * 
	 * @param nums1
	 * @param nums2
	 * @return
	 */
	public int[] intersect(int[] nums1, int[] nums2) {
		if (nums1.length == 0 || nums2.length == 0) {
			return new int[] {};
		}
		Arrays.sort(nums1);
		Arrays.sort(nums2);
		int len1 = nums1.length;
		int len2 = nums2.length;
		int[] nums = new int[Math.min(len1, len2)];
		int idx = 0;
		int idx1 = 0;
		int idx2 = 0;
		int num = Math.max(nums1[idx1], nums2[idx2]);
		while (idx1 < len1 && idx2 < len2) {
			while (idx1 < len1 && num > nums1[idx1]) {
				idx1++;
			}
			while (idx2 < len2 && num > nums2[idx2]) {
				idx2++;
			}
			if (idx1 < len1 && idx2 < len2) {
				if (nums1[idx1] == nums2[idx2]) {
					nums[idx++] = num;
					idx1++;
					idx2++;
				}
				if (idx1 < len1 && idx2 < len2) {
					num = Math.max(nums1[idx1], nums2[idx2]);
				}
			}
		}

		return Arrays.copyOfRange(nums, 0, idx);
	}
	
	public int[] intersectBetter(int[] nums1, int[] nums2) {
		if (nums1.length == 0 || nums2.length == 0) {
			return new int[] {};
		}
		Arrays.sort(nums1);
		Arrays.sort(nums2);
		int len1 = nums1.length;
		int len2 = nums2.length;
		int[] nums = new int[Math.min(len1, len2)];
		int idx = 0;
		for (int idx1 = 0, idx2 = 0; idx1 < len1 && idx2 < len2;) {
			int num1 = nums1[idx1];
			int num2 = nums2[idx2];
			if (num1 == num2) {
				nums[idx++] = num1;
				idx1++;
				idx2++;
			} else if (num1 > num2) {
				idx2++;
			} else {
				idx1++;
			}
		}
		
		return Arrays.copyOfRange(nums, 0, idx);
	}

	/**
	 * 367. 有效的完全平方数
	 * 给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
	 * @param num
	 * @return
	 */
	public boolean isPerfectSquare(int num) {
		int i = 1;
		int j = num / 100;
		while (j > 0) {
			i *= 10;
			j /= 100;
		}
		while (i < num / i) {
			i++;
		}
		if (i * i == num) {
			return true;
		}
		return false;
	}

	/**
	 * 268. 缺失数字 
	 * 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。 
	 * 
	 * 示例 1:
	 * 输入: [3,0,1] 
	 * 输出: 2 
	 * 
	 * 示例 2:
	 * 输入: [9,6,4,2,3,5,7,0,1] 
	 * 输出: 8 
	 * 
	 * 说明: 
	 * 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
	 * 
	 * @param nums
	 * @return
	 */
	public int missingNumber(int[] nums) {
		long diff = 0;
		for (int i = 0; i < nums.length; i++) {
			diff += (i+1);
			diff -= nums[i];
		}
		return (int)diff;
	}
	public int missingNumberSolution(int[] nums) {
		int len = nums.length;
		int miss = len;
		for (int i = 0; i < len; i++) {
			miss ^= nums[i];
			miss ^= i;
		}
		return miss;
	}

    /**
	 * 263. 丑数 
	 * 编写一个程序判断给定的数是否为丑数。
	 * 丑数就是只包含质因数 2, 3, 5 的正整数。
	 * 
	 * 示例 1:
	 * 输入: 6 输出: true 解释: 6 = 2 × 3 
	 * 
	 * 示例 2:
	 * 输入: 8 输出: true 解释: 8 = 2 × 2 × 2 
	 * 
	 * 示例 3:
	 * 输入: 14 输出: false 解释: 14 不是丑数，因为它包含了另外一个质因数 7。 
	 * 
	 * 说明：
	 * 1 是丑数。 输入不会超过 32 位有符号整数的范围。
	 * 
	 * @param num
	 * @return
	 */
	public boolean isUgly(int num) {
		if (num < 1) {
			return false;
		}
		while (num % 5 == 0) {
			num /= 5;
		}
		while (num % 3 == 0) {
			num /= 3;
		}
		while (num % 2 == 0) {
			num /= 2;
		}
		return num == 1;
	}
    
    /**
	 * 258. 各位相加 
	 * 给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
	 * 
	 * 示例:
	 * 输入: 38 
	 * 输出: 2 
	 * 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。 
	 * 
	 * 进阶:
	 * 你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
	 * 
	 * @param num
	 * @return
	 */
    public int addDigits(int num) {
		if (num < 10) {
			return num;
		}
		int sum = 0;
		while (num > 0) {
			sum += num % 10;
			num /= 10;
		}
		return addDigits(sum);
    }
    
    /**
	 * 242. 有效的字母异位词 
	 * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
	 * 
	 * 示例 1:
	 * 输入: s = "anagram", t = "nagaram" 
	 * 输出: true 
	 * 
	 * 示例 2:
	 * 输入: s = "rat", t = "car" 
	 * 输出: false 
	 * 
	 * 说明: 你可以假设字符串只包含小写字母。
	 * 
	 * 进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
	 * 
	 * @param s
	 * @param t
	 * @return
	 */
	public boolean isAnagram(String s, String t) {
		if (s == null || t == null) {
			return false;
		}
		char[] charArrS = s.toCharArray();
		char[] charArrT = t.toCharArray();
		int lenS = charArrS.length;
		int lenT = charArrT.length;
		if (lenS != lenT) {
			return false;
		}
		int[] sArr = new int[26];
		int[] tArr = new int[26];
		for (int i = 0; i < charArrS.length; i++) {
			sArr[charArrS[i] - 'a'] += 1;
		}
		for (int i = 0; i < charArrT.length; i++) {
			tArr[charArrT[i] - 'a'] += 1;
		}
		for (int i = 0; i < 26; i++) {
			if (sArr[i] != tArr[i]) {
				return false;
			}
		}
		return true;
	}
//	public boolean isAnagram(String s, String t) {
//		if (s == null || t == null) {
//			return false;
//		}
//		char[] charArrS = s.toCharArray();
//		char[] charArrT = t.toCharArray();
//		int lenS = charArrS.length;
//		int lenT = charArrT.length;
//		if (lenS != lenT) {
//			return false;
//		}
//		Map<Character, Integer> sMap = new HashMap<Character, Integer>();
//		Map<Character, Integer> tMap = new HashMap<Character, Integer>();
//		for (int i = 0; i < charArrS.length; i++) {
//			Character ch = charArrS[i];
//			Integer cnt = sMap.get(ch);
//			if (cnt == null) {
//				sMap.put(ch, 1);
//			} else {
//				sMap.put(ch, ++cnt);
//			}
//		}
//		for (int i = 0; i < charArrT.length; i++) {
//			Character ch = charArrT[i];
//			Integer cnt = tMap.get(ch);
//			if (cnt == null) {
//				tMap.put(ch, 1);
//			} else {
//				tMap.put(ch, ++cnt);
//			}
//		}
//		Set<Character> sKeySet = sMap.keySet();
//		Set<Character> tKeySet = tMap.keySet();
//		if (sKeySet.size() == tKeySet.size()) {
//			HashSet<Character> hashSet = new HashSet<Character>(sKeySet);
//			hashSet.removeAll(tKeySet);
//			if (hashSet.size() == 0) {
//				for (Map.Entry<Character, Integer> entry : sMap.entrySet()) {
//					Character ch = entry.getKey();
//					if (sMap.get(ch) == null || tMap.get(ch) == null || !tMap.get(ch).equals(sMap.get(ch))) {
//						return false;
//					}
//				}
//				return true;
//			}
//		}
//		return false;
//	}
    
    /**
	 * 283. 移动零 
	 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
	 * 
	 * 示例:
	 * 输入: [0,1,0,3,12] 
	 * 输出: [1,3,12,0,0] 
	 * 
	 * 说明:
	 * 必须在原数组上操作，不能拷贝额外的数组。 
	 * 尽量减少操作次数。
	 * 
	 * @param nums
	 */
	public void moveZeroes(int[] nums) {
		int len = nums.length;
		if (len <= 1) {
			return;
		}
		int i = 0;
		int k = 0; // 记录数组第一个零元素的索引
		while (i < len) {
			if (nums[i] == 0) {
				k = Math.min(k, i);
				int j = i;
				while (j < len) {
					if (nums[j] == 0) {
						j++;
					} else {
						nums[k++] = nums[j];
						nums[j] = 0;
						i = j + 1; //开始下一轮的循环
						break;
					}
				}
                if(j == len){
                    break;
                }
			} else {
				if (k != i) {
					nums[k++] = nums[i];
					nums[i] = 0;
				}else {
					k++;
				}
				i++;
			}
		}
	}
    
    /**
	 * 290. 单词模式 
	 * 给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循这种模式。
	 * 这里的 遵循 指完全匹配，例如在pattern里的每个字母和字符串 str 中的每个非空单词存在双向单映射关系。
	 * 
	 * 例如：
	 * pattern = "abba", str = "dog cat cat dog", 返回true 
	 * pattern = "abba", str = "dog cat cat fish", 返回false. 
	 * pattern = "aaaa", str = "dog cat cat dog" , 返回false. 
	 * pattern = "abba", str = "dog dog dog dog" , 返回false. 
	 * 
	 * 说明: 你可以假设 pattern 只包含小写字母， str 包含了由单个空格分开的小写单词。
	 * 
	 * @param pattern
	 * @param str
	 * @return
	 */
	public boolean wordPattern(String pattern, String str) {
		if ("".equals(pattern) && "".equals(str)) {
			return true;
		}
		String[] words = str.split(" ");
		int len = pattern.length();
		if (len != words.length) {
			return false;
		}
		Map<Character, String> mapC = new HashMap<>();
		Map<String, Character> mapS = new HashMap<>();
		for (int i = 0; i < len; i++) {
			char ch = pattern.charAt(i);
			if (!mapC.containsKey(ch)) {
				if (mapS.containsKey(words[i])) {
					return false;
				} else {
					mapC.put(ch, words[i]);
					mapS.put(words[i], ch);
				}
			} else {
				String val = mapC.get(ch);
				if (!val.equals(words[i])) {
					return false;
				}
			}
		}
		return true;
	}
    
    /**
	 * 389. 找不同 
	 * 给定两个字符串 s 和 t，它们只包含小写字母。
	 * 
	 * 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
	 * 请找出在 t 中被添加的字母。
	 * 
	 * 示例:
	 * 输入： s = "abcd" t = "abcde"
	 * 输出： e
	 * 解释： 'e' 是那个被添加的字母。
	 * 
	 * @param s
	 * @param t
	 * @return
	 */
	public char findTheDifferenceSolution(String s, String t) {
		int len = s.length();
		int diff = t.charAt(len);
		for (int i = 0; i < len; i++) {
			diff ^= s.charAt(i);
			diff ^= t.charAt(i);
		}
		return (char) diff;
	}
    public char findTheDifference(String s, String t) {
    	char[] charArrS = s.toCharArray();
    	char[] charArrT = t.toCharArray();
    	int len = charArrS.length;
    	int diff = charArrT[len];
    	for (int i = 0; i < len; i++) {
    		diff += charArrT[i];
    		diff -= charArrS[i];
    	}
    	return (char)diff;
    }
    
}
